package d_binary_search_tree.a_binary_search;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二分查找树
 * <p>
 * 这种数据结构非常适合实现字典（Map<K.V></>）的结构
 * 为了提高效率，K一般是不允许重复的
 * <p>
 * 1.每个节点的键值大于左孩子，小于右孩子。
 * 2.和堆不同， 二分搜索树可以不是一颗完全二叉树（因此不适合用数组来实现）
 * 3.K不重复
 * <p>
 * 二分搜索树的任意一个叶子为根的树也符合二分搜索树的性质
 * 因此是一个很好的递归结构
 * 非常适合使用递归的编程思想
 * <p>
 * 优化：
 * 1 二分搜索树非常适合作为字典结构来搜索key
 * 2 查找某key的前驱后继 (实现迭代器遍历的重要方法)
 * 当key存在时，小于并最接近key的key就是前驱pre
 * 当key存在时，大于并最接近key的key就是后继post
 * 当ke不存y存在时，返回null
 * 3 查找某key的上界ceil下界floor
 * 当key存在时，ceil和floor都是当前key的自身
 * 当key不存在时， 小于并最接近key的key就是下届floor
 * 当key不存在时， 大于并最接近key的key就是上届ceil
 * 4 查找某key的排名rank（key从小到大进行排名，从1开始）
 * 给Node类增加一个域统计此Node包含的其他Node的数量（叶子节点为1）
 * 这样一个node的排名就是
 * 如果node为null排名为-1
 * 如果没有父节点排名为1
 * 如果有父节点排名是父节点的
 * 5 查找某key的node存储的值时什么 - V select（K key）
 * <p>
 * 6 支持重复元素的二分搜索树
 * 为每个Node增加一个count域
 * <p>
 * <p>
 * 局限性
 * 1. 如果按顺序插入会退化成链表，查找操作的高度变成了n
 * 时间复杂度O(lgn~n) 和树高度相关
 */
@SuppressWarnings("unchecked")
public class BinarySearchTree<K extends Comparable, V> {
    private class Node {
        private K key;
        private V value;
        private Node left, right;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.left = this.right = null;
        }
    }

    private Node root;
    private int count;

    public BinarySearchTree() {
        this.root = null;
        count = 0;
    }

    public int size() {
        return count;
    }

    public boolean isEmpty() {
        return count == 0;
    }

    /**
     * 插入
     */
    public void insert(K key, V val) {
        root = insert(root, key, val);
    }

    /**
     * 向以root为根的节点中插入一个key，val的数据
     *
     * @param node
     * @param key
     * @param val
     * @return 也可以尝试实现一个非递归的练习
     */
    private Node insert(Node node, K key, V val) {
        // 如果root本身为空， 直接返回key，val的节点即可
        if (node == null) {
            count++;
            return new Node(key, val);
        }
        // 如果root不为空
        // 如果root的key和插入节点key相同，那么更改value即可，否则
        // root的key比插入节点key大，那么就递归向root的左节点插入
        // root的key比插入节点key小，那么就递归向root的右节点插入
        if (node.key.compareTo(key) == 0) {
            node.value = val;
        } else if (node.key.compareTo(key) > 0) {
            node.left = insert(node.left, key, val);
        } else {
            node.right = insert(node.right, key, val);
        }
        return node;
    }

    // 查找二叉搜索树中是否包含键key
    public boolean containKey(K key) {
        return containKey(root, key);
    }

    /**
     * 查找以node的为根的二叉搜索树中是否包含键key
     *
     * @param node
     * @param key
     * @return
     */
    private boolean containKey(Node node, K key) {
        if (node == null) return false;
        if (node.key.compareTo(key) == 0) {
            return true;
        } else if (node.key.compareTo(key) > 0) {
            return containKey(node.left, key);
        } else {
            return containKey(node.right, key);
        }
    }

    // 查找二叉搜索树中以key为键对应的值
    public V findValueByKey(K key) {
        return findNodeByKey(root, key).value;
    }

    /**
     * 查找以node为根的二叉搜索树中以key为键对应的值
     *
     * @param node
     * @param key
     * @return 不存在返回null
     */
    private Node findNodeByKey(Node node, K key) {
        if (node == null) return null;
        if (node.key.compareTo(key) == 0) {
            return node;
        } else if (node.key.compareTo(key) > 0) {
            return findNodeByKey(node.left, key);
        } else {
            return findNodeByKey(node.right, key);
        }
    }

    // 前序遍历
    public void preOrder() {
        preOrder(root);
        System.out.println();
    }

    /**
     * 前序遍历
     * 1. 打印节点值
     * 2. 递归访问左子树
     * 3. 递归访问右子树
     * 特点：按照插入节点的顺序进行打印
     *
     * @param root
     */
    private void preOrder(Node root) {
        if (root != null) {
            System.out.print(root.key + "->" + root.value + "\t");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    // 中序遍历
    public void inOrder() {
        inOrder(root);
        System.out.println();
    }

    /**
     * 中序遍历
     * 1. 递归访问左子树
     * 2. 打印节点值
     * 3. 递归访问右子树
     * 特点：可以按照key从小到大的顺序打印对应value
     *
     * @param root
     */
    private void inOrder(Node root) {
        if (root != null) {
            inOrder(root.left);
            System.out.print(root.key + "->" + root.value + "\t");
            inOrder(root.right);
        }
    }

    // 后序遍历
    public void postOrder() {
        postOrder(root);
        System.out.println();
    }

    /**
     * 后序遍历
     * 1. 递归访问左子树
     * 2. 递归访问右子树
     * 3. 打印节点值
     * 特点：先倒序打印完左右子树的节点最后再打印根节点
     * 在c++的析构函数中释放节点资源时适合使用后序遍历
     *
     * @param root
     */
    private void postOrder(Node root) {
        if (root != null) {
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.key + "->" + root.value + "\t");
        }
    }

    // 层序遍历
    public void levelOrder() {
        levelOrder(root);
    }

    /**
     * 层序遍历 - 广度优先遍历
     * 利用队列暂存输出内容
     * 可以实现从上层到下层的输出
     * 称为广度优先
     *
     * @param root
     */
    private void levelOrder(Node root) {
        if (root == null) return;
        Queue<Node> q = new LinkedList<>();
        q.offer(root); // 添加到队列
        while (!q.isEmpty()) {
            Node node = q.poll();  // 队首出队并返回
            System.out.print(node.key + "->" + node.value + "\t"); // 打印队首
            if (node.left != null) q.offer(node.left); // 入队左节点到队尾
            if (node.right != null) q.offer(node.right); // 入队右节点队尾
        }
    }

    // 寻找最小键值
    public K getMinKey() {
        assert count != 0;
        return getNodeByMinKey(root).key;
    }

    /**
     * 对以root为根的二分搜索树中寻找最小键值
     * 递归寻找root的最后一个没有孩子的左孩子
     *
     * @param root
     * @return
     */
    private Node getNodeByMinKey(Node root) {
        if (root.left == null) return root;
        return getNodeByMinKey(root.left);
    }

    // 寻找最大键值
    public K getMaxKey() {
        return getMaxKey(root).key;
    }

    /**
     * 对以root为根的二分搜索树中寻找最大键值
     * 递归寻找root的最后一个没有孩子的右孩子
     *
     * @param root
     * @return
     */
    private Node getMaxKey(Node root) {
        if (root.right == null) return root;
        return getMaxKey(root.right);
    }

    // 删除最小key的节点
    public K removeMin() {
        assert count != 0;
        return removeByMinKey(root).key;
    }

    /**
     * 删除以node为根最小key的节点
     *
     * @param node
     * @return
     */
    private Node removeByMinKey(Node node) {
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            count--;
            return rightNode;
        }
        node.left = removeByMinKey(node.left);
        return node;
    }

    // 删除最大key的节点
    public K removeMax() {
        assert count != 0;
        return removeMax(root).key;
    }

    /**
     * 删除以node为根最大key的节点
     *
     * @param node
     * @return
     */
    private Node removeMax(Node node) {
        if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            count--;
            return leftNode;
        }
        node.right = removeMax(node.right);
        return node;
    }

    // 删除指定key值对应的节点
    public void removeByKey(K key) {
        root = removeByKey(root, key);
    }

    /**
     * 删除以node为根的指定key的节点
     * 返回删除节点后新的node的引用
     *
     * @param node
     * @param key
     * @return
     */
    private Node removeByKey(Node node, K key) {

        if (node == null) return null; // 节点为空， 直接返回

        if (node.key.compareTo(key) > 0) { // key小于待删除根节点key， 向左递归
            node.left = removeByKey(node.left, key);
            return node;
        }

        if (node.key.compareTo(key) < 0) { // key大于待删除根节点key， 向右递归
            node.right = removeByKey(node.right, key);
            return node;
        }

        // 剩下的情况就是 key 正好等于 待删除根节点key - 执行删除操作， 分为以下三钟情况考虑

        // 1. 只有右子树 - 将待删除节点指向其右子树
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null; // 释放资源
            count--;
            return rightNode;
        }
        // 2. 只有左子树 - 将待删除节点指向其左子树
        if (node.right == null) {
            Node leftNode = node.left;
            node.left = null; // 释放资源
            count--;
            return leftNode;
        }
        // 3. 既有左子树又有右子树 - 这种情况最为复杂， 分三步完成
        // a. 获取右子树的最小值（也可以是左子树的最大值）的节点作为新节点的根
        Node newNode = getNodeByMinKey(node.right);
        // b. 新节点的右子树指向待删除节点的右子树，此时这个右子树中的最小值已经被删除
        newNode.right = removeByMinKey(node.right); // removeMin中已经有count--了
        // c. 新节点的左孩子引用指向待删除节点的左子树
        newNode.left = node.left;
        node.left = node.right = null; // 解除待删除节点的引用，让垃圾回收机制自动释放node资源
        return newNode; // 返回新节点
    }


    // 查找某个key的前驱节点的key
    // 一个节点的前驱节点是其左子树中的最大值，若无左子树，其前驱节点在从根节点到key的路径上，比key小的最大值。
    public K predecessor(K key) {
        Node node = findNodeByKey(root, key);

        // node不存在
        if (node == null)
            return null;
        //  左子树存在
        if (node.left != null)
            return getMaxKey(node.left).key;
        // 否则找到右子树包含目标节点的最小树的根
        Node preNode = getPreNode(root, key);
        return preNode == null ? null : preNode.key;
    }

    /**
     * 递归逻辑如下：
     * 1 从根节点开始，如果大于目标向左递归查找，如果等于目标返回null
     * 2 如果key小于目标，向右递归查找,同时检查递归函数的返回值
     *      a.找到第一个返回null的递归过程（说明子递归过程已经发现了目标key），返回当前递归过程的节点
     *      b.如果返回值不是null，说明上一个递归过程已经找到目标，将上一个递归过程的结果向上传递即可
     *
     * 简单说就是找到右子树包含目标节点的最小树的根
     *
     * 注意！ key的节点假设一定存在，因此调用此函数之前务必验证这点！
     *
     *
     * @param node
     * @param key
     * @return
     */
    private Node getPreNode(Node node, K key) {
        if (node.key.compareTo(key) == 0) { // 正好是key所在节点 终止并返回null
            return null;
        } else if (node.key.compareTo(key) > 0) { // 比key大 向左子树查找
            return getPreNode(node.left, key);
        } else { // 比key小 向右子树查找
            Node tempNode = getPreNode(node.right, key);
            // 如果tempNode为null 说明当前node的右子树包含目标节点，直接返回当前node即可
            return tempNode == null ? node : tempNode;
        }
    }

    // 查找某个key的后继节点的key
    // 一个节点的后继节点是其右子树中的最小值，若无右子树，其前驱节点在从根节点到key的路径上，比key大的最小值。
    public K successor(K key) {
        Node node = findNodeByKey(root, key);

        // node不存在
        if (node == null)
            return null;
        //  右子树存在 取右子树的最小值
        if (node.right != null)
            return getNodeByMinKey(node.right).key;
        // 否则找到左子树包含目标节点的最小树的根
        Node nextNode = getNextNode(root, key);
        return nextNode == null ? null : nextNode.key;
    }

    /**
     * 递归逻辑如下：
     * 1 从根节点开始，如果小于目标向右递归查找，如果等于目标返回null
     * 2 如果key大于目标，向左递归查找,同时检查递归函数的返回值
     *      a.找到第一个返回null的递归过程（说明子递归过程已经发现了目标key），返回当前递归过程的节点
     *      b.如果返回值不是null，说明上一个递归过程已经找到目标，将上一个递归过程的结果向上传递即可
     *
     * 简单说就是找到左子树包含目标节点的最小树的根
     *
     * 注意！ key的节点假设一定存在，因此调用此函数之前务必验证这点！
     *
     * @param node
     * @param key
     * @return
     */
    private Node getNextNode(Node node, K key) {
        if (node.key.compareTo(key) == 0) { // 正好是key所在节点 终止并返回null
            return null;
        } else if (node.key.compareTo(key) < 0) { // 比key小 向右搜索路径
            return getNextNode(node.right, key); // 肯定不存在目标节点
        } else { // 比key大 向左搜索路径
            Node tempNode = getNextNode(node.left, key);
            // 如果tempNode为null 说明当前node的左节点的key就是目标，直接返回当前node即可
            return tempNode != null ? tempNode : node;
        }
    }
}

